package Z.dailyExercise.March;

import java.util.List;

public class _148排序链表 {

    /**
     * 题解：链表的归并排序
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        return sortList(head, null);



    }
    /**
     * 分化 递归的终止条件 节点个数《=1 对应的归并 left》=right
     *
     * 因为listNode 传入的时候已经包含start 所以可以省掉部分参数
     */
    public ListNode sortList(ListNode head,ListNode end){
        if (head == null){
            return head;
        }
        if (head.next == end){
            head.next = null;
            return head;
        }

        //利用快慢指针来获取mid
        ListNode slow = head,fast = head;
        while (fast != end){
            slow = slow.next;
            fast = fast.next;
            if (fast != end){
                fast = fast.next;
            }
        }

        ListNode mid = slow;
        ListNode l = sortList(head,mid);
        ListNode r = sortList(mid.next,end);

        ListNode sort = merge(l,r);
        return sort;

    }

    public ListNode merge(ListNode l,ListNode r){
        ListNode dummyHead = new ListNode(0);
        ListNode temp=dummyHead,temp1 =l,temp2 = r;

        while (temp1 != null && temp2 != null){
            if (temp1.val < temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }

        while (temp1 != null){
            temp.next = temp1;
        }
        while (temp2 != null){
            temp.next = temp2;
        }

        return dummyHead.next;
    }

}
